// 原不重复,不重复选,选取排列其中n个字符.swap方法[排列组合]
#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

// ============ 排列
class Solution_swap {
 private:
  // cur : 当前编号
  // k : require length
  void dfs_swap(size_t cur, size_t k, vector<char>& vec,
                vector<vector<char>>& ans) {
    if (cur >= vec.size()) {
      return;
    }
    if (cur == k - 1) {
      ans.push_back(vec);
      return;
    }
    for (size_t i = cur; i < vec.size(); i++) {
      swap(vec[i], vec[cur]);
      dfs_swap(cur + 1, k, vec, ans);
      swap(vec[i], vec[cur]);
    }
  }

 public:
  vector<string> permutation(string S) {
    vector<vector<char>> vOut;
    std::sort(S.begin(), S.end());
    // 转成 vector<char>
    vector<char> s2;
    for (auto c : S) s2.push_back(c);
    dfs_swap(0, S.length(), s2, vOut);
    // 转换成 vector<string>
    vector<string> res;
    for (auto vo : vOut) {
      string st;
      for (auto c : vo) st += c;
      res.push_back(st);
    }
    return res;
  }
};

// int main()
//{
//    Solution sol;
//    auto vtOut = sol.findRedundantConnection({});
//    for (auto n : vtOut) PF("%d,",n); PF("\n");
//    return 0;
//}
